#pragma once

#include "ezstl_iterator_base.hpp"
namespace ezstl {

template <typename InputIterator, typename T>
T accumulate(InputIterator first, InputIterator last, T init) {
  for (; first != last; ++first) init = init + *first;
  return init;
}

template <typename InputIterator, typename T, typename BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init,
             BinaryOperation binary_op) {
  for (; first != last; ++first) init = binary_op(init, *first);
  return init;
}

/**
 * @brief 计算相邻元素之间的差值，采用就地运算方式时，也就是 result == first 这是一个(mutating algorithm)
 *
 * @tparam InputIterator
 * @tparam OutputIterator
 * @param first
 * @param last
 * @param result
 * @return OutputIterator
 */
template <typename InputIterator, typename OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result) {
  using value_type = typename ezstl::iterator_traits<InputIterator>::value_type;

  if (first == last) return result;

  *result = *first;
  value_type value = *first;
  while (++first != last) {
    value_type tmp = *first;
    *++result = tmp - value;
    value = tmp;
  }
  return ++result;
}

template <typename InputIterator, typename OutputIterator,
          typename BinaryOperation>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result,
                                   BinaryOperation binary_op) {
  using value_type = typename ezstl::iterator_traits<InputIterator>::value_type;
  if (first == last) return result;
  *result = *first;
  value_type value = *first;
  while (++first != last) {
    value_type tmp = *first;
    *++result = binary_op(tmp, value);
    value = tmp;
  }
  return ++result;
}

/**
 * @brief 内积
 *
 * @tparam T
 * @param first1
 * @param last1
 * @param first2
 * @param init
 * @return T
 */
template <typename InputIterator1, typename InputIterator2, typename T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init) {
  for (; first1 != last1; ++first1, (void)++first2)
    init = init + (*first1 * *first2);
  return init;
}

/**
 * @brief 内积
 *
 * @param first1
 * @param last1
 * @param first2
 * @param init
 * @param binary_op1 Function object to accumulate with.
 * @param binary_op2 Function object to apply to pairs of input values.
 * @return T
 */
template <typename InputIterator1, typename InputIterator2, typename T,
          typename BinaryOperation1, typename BinaryOperation2>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init, BinaryOperation1 binary_op1,
                BinaryOperation2 binary_op2) {
  for (; first1 != last1; ++first1, (void)++first2)
    init = binary_op1(init, binary_op2(*first1, *first2));
  return init;
}

/**
 * @brief 部分和，将 *first 赋值给 *result，将 *first + *(first + 1) 赋值给
 * *(result + 1)，以此类推
 *
 * @tparam InputIterator
 * @tparam OutputIterator
 * @param first
 * @param last
 * @param result
 * @return OutputIterator
 */
template <typename InputIterator, typename OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result) {
  using value_type = typename iterator_traits<InputIterator>::value_type;
  if (first == last) return result;
  value_type value = *first;
  *result = *first;
  while (++first != last) {
    value = value + *first;
    *++result = value;
  }
  return ++result;
}

template <typename InputIterator, typename OutputIterator,
          typename BinaryOperation>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result, BinaryOperation binary_op) {
  using value_type = typename iterator_traits<InputIterator>::value_type;
  if (first == last) return result;
  value_type value = *first;
  *result = *first;
  while (++first != last) {
    value = binary_op(value, *first);
    *++result = value;
  }
  return ++result;
}

/**
 * @brief 计算某数的n幂次(乘幂)
 * 
 * @tparam T 
 * @tparam Integer 
 * @param x 
 * @param n 
 * @return T 
 */
template<typename T, typename Integer>
inline T power(T x, Integer n) {
  T result = 1;
  while (n > 0) {
    if (n & 1) result *= x;
    x *= x;
    n >>= 1;
  }
  return result;
}

template<typename T, typename Integer, typename  MonoidOperation>
T power(T x, Integer n, MonoidOperation op) {
  if (n == 0) return identity_element(op); // TODO: impl identity_element
  while ((n & 1) == 0) {
    n >>= 1;
    x = op(x, x);
  }

  T result = x;
  n >>= 1;
  while (n > 0) {
    x = op(x, x);
    if (n & 1) result = op(result, x);
    n >>= 1;
  }
  return result;
}

template<typename ForwardIterator, typename T>
void iota(ForwardIterator first, ForwardIterator last, T value) {
  for (; first != last; ++first) {
    *first = value;
    ++value;
  }
}


}  // namespace ezstl